#include <vector>
#include <queue>
#include <stack>
#include <iostream>

struct ActivityTime {
	enum TimeType {start, finish};
	int time;
	TimeType type; //0:start 1:finish
	int activity_id; //0 .. n-1
	void init(int t, TimeType tt, int id)  {
		time = t;
		type = tt; 
		activity_id = id;
	}
};

struct ActivityComp {
	bool operator() ( const ActivityTime& lhs, const ActivityTime& rhs) {
		if (lhs.time < rhs.time)
			return true;
		else if (lhs.time == rhs.time) {
			if (lhs.type == ActivityTime::start && rhs.type == ActivityTime::finish) //if time is the same, finish before start
				return false;
			else if(lhs.type == ActivityTime::finish && rhs.type == ActivityTime::start)
				return true;
			else
				return lhs.activity_id < rhs.activity_id;
		}
		else
			return false;
	}
};

struct Hall {
	void init(int id)  {
		hall_id = id;
		used = false;
	}
	int hall_id;
	bool used;
	std::queue<int> activity_queue;
};

void schedule_activities(std::vector<ActivityTime>& at, std::vector<Hall>& h, std::stack<int>& free_hall, std::vector<int>& a2h) {
	ActivityComp ac;
	std::sort(at.begin(), at.end(), ac);
	for (std::vector<ActivityTime>::iterator iter = at.begin(); iter!=at.end(); ++iter) {
		if(iter->type == ActivityTime::start) {
			a2h[iter->activity_id] = free_hall.top();
			free_hall.pop();
			h[a2h[iter->activity_id]].used = true;
			h[a2h[iter->activity_id]].activity_queue.push(iter->activity_id);
		}
		else if(iter->type == ActivityTime::finish){
			free_hall.push(a2h[iter->activity_id]);
		}
		else {
			throw std::logic_error(std::string("Unknown Activity Type"));
		}
	}
}

void print_schedule(std::vector<Hall>& h, std::stack<int>& free_hall,int * sa, int * fa) {
	while(!free_hall.empty()) {
		int hall_id = free_hall.top();
		free_hall.pop();
		if(h[hall_id].used == false)
			break;
		std::cout << "Hall[" << hall_id << "] : ";
		while(!h[hall_id].activity_queue.empty() ) {
			int activity_id = h[hall_id].activity_queue.front();
			h[hall_id].activity_queue.pop();
			std::cout << "A[" << activity_id << "](" << sa[activity_id] << ',' << fa[activity_id] << ") ";
		}
		std::cout << std::endl;
	}
}

void test_activity_scheduling(){
	int sa[] = {1,3,0,5,3,5,6,8,8,2,12};
	int fa[] = {4,5,6,7,9,9,10,11,12,14,16};
	int n = sizeof(sa)/sizeof(int);
	std::vector<ActivityTime> at(2*n);
	for (int i = 0; i < n; ++i){
		at[2*i].init(sa[i], ActivityTime::start, i);
		at[2*i+1].init(fa[i], ActivityTime::finish, i);
	}
	std::vector<int> a2h(n);
	std::vector<Hall> h(n);
	std::stack<int> free_hall;
	for (int i = n-1; i >= 0; --i) {
		h[i].init(i);
		free_hall.push(i);
	}
	schedule_activities(at,h,free_hall, a2h);
	print_schedule(h,free_hall,sa,fa);
}